package com.lga.algorithm;

/**
 * leetCode 5. 最长回文子串
 *
 * @author lga
 */
public class LongestPalindrome {

    public String longestPalindrome(String s) {

        String longestStr = "";
        int maxLength = 0;
        int start = 0;
        int end = 0;
        if (s.length() == 0 || s == "") {
            return "";
        }
        if (s.length() == 1) {
            return s;
        }
        for (int i = 0; i < s.length(); i++) {
            //回文子串个数为奇数时
            int i1 = expandAroundCenter(s, i, i);
            //回文子串为偶数时
            int i2 = expandAroundCenter(s, i, i + 1);
            //获取最长子串的个数
            int len = Math.max(i1, i2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
            longestStr = s.substring(start, end + 1);
        }

        /* *//**
         * 暴力解法
         *//*
        for (int i = 0; i < s.length(); i++) {
            for (int j = i+1; j <=s.length() ; j++) {
                String tempStr = s.substring(i, j);
                StringBuilder reverseStr = new StringBuilder(tempStr).reverse();
                if (tempStr.equals(reverseStr.toString())) {
                    if (maxLength < tempStr.length()) {
                        maxLength = maxLength > tempStr.length() ? maxLength : tempStr.length();
                        longestStr = s.substring(i, j);
                    }
                }
            }
        }*/
        return longestStr;
    }

    /**
     * 中心扩展算法
     * 求出以left和right为中心向左右扩展得到的还是回复的最大长度
     *
     * @param s
     * @param left
     * @param right
     * @return
     */
    public static int expandAroundCenter(String s, int left, int right) {

        if (left < right) {
            while (left > 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            return right - left + 1;
        }
        while (left > 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;

    }

    public static void main(String[] args) {
        System.out.println(new LongestPalindrome().longestPalindrome("babad"));
    }
}
